package a12_SeqList.SingleLinkedListWithHead;

import a12_SeqList.ArrayList.SeqList;

import javax.xml.soap.Node;

/**
 * @Author quan
 * @Description 带头单链表的实现：最大的好处就是不用考虑头结点是否为空等特殊情况，因为前面一直有一个虚拟的头结点
 * @Date 2023/3/21 17:13
 */
public class SLinkedWithHead<E> implements SeqList<E> {
    //创建单链表的虚拟头结点，但是不存储具体元素
    private Node dummyHead = new Node(null);
    private int size;
    private class Node{
        E val;
        Node next;
        //构造方法
        Node(E val) {
            this.val = val;
        }
        public Node(E val, Node next) {
            this.val = val;
            this.next = next;
        }
    }
    /**
     * 头插
     */
    public void addFirst(E element) {
        add(0,element);
    }
    /**
     * 尾插
     */
    @Override
    public void add(E element) {
        add(size,element);
    }
    /**
     * 正常位置的插入
     */
    @Override
    public void add(int index, E element) {
        //判断索引的合法性
        if(!indexCheck(index)){
            throw new IllegalArgumentException("add index illegal!");
        }
        //取临时的值代替虚拟头结点
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        //此时的Prev就是索引位置的前驱
        //产生新的值为element的节点
        Node node = new Node(element);
        //更改指向
        node.next = prev.next;
        prev.next = node;
        //更新节点数
        size++;
    }
    /**
     * 检查索引的合法性
     */
    private boolean indexCheck(int index) {
        if(index < 0 || index > size){
            return false;
        }
        return true;
    }

    @Override
    public E removeByIndex(int index) {
        return null;
    }

    @Override
    public void removeByValue(E element) {

    }
    /**
     * 删除所有值为element的元素
     */
    @Override
    public void removeAllValue(E element) {
        //用临时节点代替head进行操作
        Node prev = dummyHead;
        while (prev.next !=null){
            if(prev.next.val.equals(element)){
                prev.next = prev.next.next;
                size--;
            }else{
                prev=prev.next;//这里的操作同 单链表一样，只有下一个节点的值和element不相等的时候，才移动指针。否则会造成元素的漏删
            }
        }
    }

    @Override
    public E set(int index, E elemnet) {
        return null;
    }

    @Override
    public E get(int index) {
        return null;
    }

    @Override
    public boolean contains(E element) {
        return false;
    }

    @Override
    public int indexOf(E element) {
        return 0;
    }
    /**
     * 重写toString方法
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (Node x = dummyHead.next; x!=null ; x=x.next) {
            sb.append(x.val).append("——>");
            if(x.next == null){
                sb.append("Null");
            }
        }
        return sb.toString();
    }
}
